package problem4_Median_of_Two_Sorted_Arrays;

public class MySolution {
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int m = nums1.length;
		int n = nums2.length;
		if ((m + n) % 2 == 0) {
			return (findKth((m + n) / 2, nums1, 0, nums2, 0) + findKth((m + n) / 2 + 1, nums1, 0, nums2, 0)) / 2.0;
		} else {
			return findKth((m + n) / 2 + 1, nums1, 0, nums2, 0);
		}
	}

	private double findKth(int k, int[] a, int aStart, int[] b, int bStart) {
		if (aStart >= a.length) {
			return b[bStart + k - 1];
		}
		if (bStart >= b.length) {
			return a[aStart + k - 1];
		}
		if (k == 1) {
			return Math.min(a[aStart], b[bStart]);
		}
		int aMid = aStart + k / 2 - 1;
		int bMid = bStart + k / 2 - 1;

		int aValue = aMid < a.length ? a[aMid] : Integer.MAX_VALUE;
		int bValue = bMid < b.length ? b[bMid] : Integer.MAX_VALUE;

		if (aValue < bValue) {
			return findKth(k - k / 2, a, aMid + 1, b, bStart);
		} else {
			return findKth(k - k / 2, a, aStart, b, bMid + 1);
		}

	}
}
